package q6190_goodIndices;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    /*
    分别考虑两个问题：
    首先是如何满足：下标 i 之前 的 k 个元素是 非递增的 。
    维护一个left数组，采用动态规划的方式，如果nums[i] <= nums[i - 1] 也就是出现了非递增
    那么left[i] = left[i - 1] + 1; 因此 如果对于一个位置i 其前面left[i - 1]达到了k
    也就意味着其前面的k个元素都是非递增的 否则达不到k
    同样的维护一个right数组即可
    然后考察 k -> n - k 的每一个位置 是否满足left[i - 1] >= k && right[i + 1] >= k
     */
    public List<Integer> goodIndices(int[] nums, int k) {
        int n = nums.length;
        int[] left = new int[n], right = new int[n];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for (int i = 1; i < n; i++) {
            if (nums[i] <= nums[i - 1]) left[i] = left[i - 1] + 1;
            if (nums[n - 1 - i] <= nums[n - i]) right[n - i - 1] = right[n - i] + 1;
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = k; i < n - k; i++) {
            if (left[i - 1] >= k && right[i + 1] >= k) ans.add(i);
        }

        return ans;
    }
}
